package a09_贪心算法;

import java.util.Arrays;

/**
 * <p>
 * a11_加油站复习2
 * </p>
 *
 * @author flyduck
 * @since 2025/2/19
 */
public class a11_加油站复习2 {

    public static void main(String[] args) {
        a11_加油站复习2 test = new a11_加油站复习2();
        System.out.println(test.canCompleteCircuit(new int[]{2, 5, 2, 3, 5}, new int[]{1, 2, 8, 2, 4}));
    }
    //题目中说：如果有解，解是唯一的
    //从0开始
    //gas               2,5,2,3,5
    //casts             1,2,8,2,4
    //经过此站剩余的油量 1,4,-2

    //从下标3开始
    //gas               2,5,2,3,5
    //casts             1,2,8,2,4
    //经过此站剩余的油量 3,6,0,1,2



    //经验总结：如何遍历环
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int[] diff = new int[gas.length];
        for (int i = 0; i < diff.length; i++) {
            diff[i] = gas[i] - cost[i];
        }

        if (Arrays.stream(diff).sum() < 0) {
            return -1;
        }

        int startIdx = 0;
        int currentIdx = startIdx;
        int sum = 0;
        while (true){
            sum += diff[currentIdx];
            if(sum < 0){
                startIdx =  currentIdx + 1;
                currentIdx = startIdx;
                sum = 0;
            }else {
                //迭代下一个
                if(currentIdx == diff.length-1){
                    currentIdx = 0;
                }else {
                    currentIdx++;
                }

                //如果下一个是自己，那么就停止了
                if(currentIdx == startIdx){
                    break;
                }
            }
        }
        return startIdx;

    }
}
